package com.longge;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @program: my-code
 * @description:
 * @author: longge
 * @create: 2021-03-06 23:15
 */
public class PrintTree {
    List<List<String>> list = new ArrayList<>();

    public List<List<String>> printTree(TreeNode root) {
        if (root == null) return null;
        int height = dfs(root);
        String[][] res = new String[height][(1 << height) - 1];
        for (String[] arr : res)
            Arrays.fill(arr, "");
        List<List<String>> ans = new ArrayList<>();
        dfs(res, root, 0, 0, res[0].length);
        for (String[] arr : res)
            ans.add(Arrays.asList(arr));
        return ans;
    }

    void dfs(String[][] res, TreeNode root, int row, int l, int r) {
        if (root == null) return;
        //column 当前二叉树节点
        int column = (l + r) / 2;
        res[row][column] = String.valueOf(root.val);
        //区间[l,column-1] 左子树节点
        dfs(res, root.left, row + 1, l, column - 1);
        //区间[column + 1,r 右子树节点
        dfs(res, root.right, row + 1, column + 1, r);
    }

    int dfs(TreeNode root) {
        if (root == null) return 0;
        int l = dfs(root.left) + 1;
        int r = dfs(root.right) + 1;
        return Math.max(l, r);
    }
}
